package com.aqie.arithmetic.sort;

/**
 * 归并排序
 */
public class MergeSort extends SortTest{
    // 归并所需的辅助数组
    private static Comparable[] aux;

    /**
     * 自顶向下的归并排序
     * @param a
     */
    @Override
    public void sort(Comparable[] a) {
        // 一次性分配空间
        aux = new Comparable[a.length];
        sort(a, 0, a.length - 1);
    }

    private void sort(Comparable[] a, int l, int h) {
        if (h <= l) return;
        int mid = l + (h - l) / 2;
        sort(a, l, mid);       // 左半边排序
        sort(a,mid + 1, h); // 右半边排序
        merge(a, l, mid , h);
    }


    // 原地归并的抽象方法
    public static void merge(Comparable[] a, int l, int mid, int h){
        int i = l, j = mid + 1;
        for (int k = l; k <= h; k++){
            aux[k] = a[k];
        }

        for (int k = l; k <= h; k++){
            if (i > mid) a[k] = aux[j++];
            else if (j > h) a[k] = aux[i++];
            else if(less(aux[j], aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }

    public static void main(String[] args) {
        new MergeSort().process(100000);
    }

}
